class Solution {
public:
    /*
     * @param start: a string
     * @param end: a string
     * @param dict: a set of string
     * @return: An integer
     */
    
    //个：从词向字典变化bfs（适用于字典比较小）
    // int check(string s, string t)
    // {
    //     if (s.length() != t.length()) return false;
    //     int cnt = 0;
    //     for (int i = 0; i < s.size(); ++i)
    //     {
    //         if (s[i] != t[i]) cnt++;
    //         if (cnt > 1) return false;
    //     }
    //     return true;
    // }
    // int ladderLength(string &start, string &end, unordered_set<string> &dict) {
    //     deque<string> target; //dequeue同时支持queue（先进先出）和vector（遍历）
    //     target.push_back(end);
    //     int times = 1;
    //     bool hasAns = false;
    //     for (auto d: dict)
    //     {
    //         if (check(d, start)) 
    //         {
    //             hasAns = true;
    //             break;
    //         }
    //     }
    //     if (dict.size() == 1) return 2; //题目好像有bug
    //     if (!hasAns) return 0;
    //     bool find = false;
    //     while (true)
    //     {
    //         times++;
    //         int s = target.size(); //用queue的话要注意变长
    //         for (int i = 0; i < s; ++i)
    //         {
    //             string t = target.front();
    //             target.pop_front();
    //             dict.erase(t);
    //             for (unordered_set<string>::iterator it = dict.begin(); it != dict.end(); ++it)
    //             {
    //                 if (check(*it, t))
    //                 {
    //                     target.push_back(*it);
    //                 }
    //             }
    //             for (auto t: target) //1.要删除添加过的，不然超时 2.不能在迭代器内部删除
    //             {
    //                 dict.erase(t);
    //             }
    //         }
    //         int ttimes = times + 1;
    //         for (string t: target)
    //         {
    //             if (t == start || check(t, start)) 
    //             {
    //                 find = true;
    //                 if (t == start) return times;
    //             }
    //         }
    //         if (find) return ttimes;
    //     }
    //     return times;
    // }
    
    
    
    // 法二：修改字母bfs
    int ladderLength(string &start, string &end, unordered_set<string> &dict) {
        int result = 1;
        deque<string> record;
        record.push_back(start);
        while (!record.empty())
        {
            int len = record.size();
            result++;
            for (int l = 0; l < len; ++l)
            {
                string tmp = record.front();
                record.pop_front();
                dict.erase(tmp);
                for (int i = 0; i < tmp.size(); ++i)
                {
                    for (int j = 0; j < 26; ++j)
                    {
                        if (char('a' + j) == tmp[i]) continue;
                        string ttmp = tmp;
                        ttmp[i] = char('a' + j); //不要忘了转换char！！！
                        if (ttmp == end) return result;
                        if (dict.find(ttmp) != dict.end()) 
                        {
                            record.push_back(ttmp);
                            dict.erase(ttmp);
                        }
                    }
                }
            }
        }
        return result;
    }
};